package datastruct.sort;

import java.util.Arrays;

/**
 * @program: DataStructuresAndAlgorithms
 * @description: 基数排序
 * @author: zhang
 * @create: 2020-03-13 16:38
 */
public class RadixSort {


    public static void radixSort(int[] arr) {
        int max = arr[0];
        for (int i = 1; i < arr.length; i++) {
            if (arr[i] > max) {
                max = arr[i];
            }
        }
        int maxLength = (max + "").length();

        for (int i = 0, n = 1; i < maxLength; i++, n *= 10) {
            //第i轮（针对每个元素对应的位进行处理）各位 十位 百位 千位
            //定义一个二维数组，表示10个桶，每个桶就是一个一维数组
            //1、二维数组包含10个一维数组
            //2、为了防止数据溢出，则每一个一维数组（桶），大小为 arr.length
            //3、空间换时间的经典算法
            int[][] bucket = new int[10][arr.length];

            //为了记录每一个桶中，实际存放了多少个数据，我们定义一个一维数组来记录各个桶的每次放入的数据个数
            //bucketElementCounts[i] 记录i桶放入的元素个数
            int[] bucketElementCounts = new int[10];

            //遍历数组，取出个位数进行排序处理
            for (int j = 0; j < arr.length; j++) {
                //取出每个元素的个数
                int digitOfElement = arr[j] / n % 10;
                bucket[digitOfElement][bucketElementCounts[digitOfElement]] = arr[j];
                bucketElementCounts[digitOfElement]++;
            }

            int index = 0;
            //按照这个桶的顺序（一维数组的下标依次取出数据，放入原来数据）
            for (int k = 0; k < bucketElementCounts.length; k++) {
                if (bucketElementCounts[k] != 0) {
                    for (int l = 0; l < bucketElementCounts[k]; l++) {
                        arr[index++] = bucket[k][l];
                    }
                }
                bucketElementCounts[k] = 0;
            }
            //第i+1轮处理后，需要将每个 bucketElementCounts[k] = 0 ！！！！
//            System.out.println(Arrays.toString(arr));
        }
    }

    public static void main(String[] args) {
//        int[] arr = {53, 3, 542, 748, 14, 214};
        int[] arr = new int[100000000];
        for (int i = 0; i < 100000000; i++) {
            arr[i] = (int) (Math.random() * 80000000); //生成[0,80000000]
        }
        long start = System.currentTimeMillis();

        radixSort(arr);

        System.out.println(System.currentTimeMillis() - start);
        System.out.println(arr.length);
//        System.out.println(Arrays.toString(arr));
    }
}